package algorithm.sort.review2;

import java.util.Arrays;

public class quick {
    public static void main(String[] args) {
        int[] arr = {3, 3, 4, 1, 3, 56, 242, 1};
//        quick(arr,0, arr.length-1);
        quickReview(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }

    public static void quick(int[] arr, int left, int right) {
        if (left < right) {
            int l = left;
            int r = right;
            int pivot = arr[left];
            while (l < r) {
                while (r > l && arr[r] >= pivot) {
                    r--;
                }
                if (l == r)
                    break;
                arr[l++] = arr[r];
                while (l < r && arr[l] <= pivot) {
                    l++;
                }
                if (l == r)
                    break;
                arr[r--] = arr[l];
            }
            arr[l] = pivot;
            //左边
            quick(arr, left, l - 1);
            quick(arr, l + 1, right);
        }
    }


    public static void quickReview(int[] arr, int left, int right) {
        if (left > right)
            return;
        int l = left;
        int pivot = arr[left];
        int r = right;
        while (l < r) {
            while (l < r && arr[r] >= pivot) {
                r--;
            }
            if (l == r)
                break;
            arr[l++] = arr[r];
            while (l < r && arr[l] <= pivot) {
                l++;
            }
            if (l == r)
                break;
            arr[r--] = arr[l];
        }
        arr[l] = pivot;
        //左递归
        quickReview(arr, left, l - 1);
        //右递归
        quickReview(arr, l + 1, right);
    }
}
